package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * leetcode 51. N 皇后
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/15 8:55
 */
public class E51 {
    /*
        0  1  2  3  4
     0  a  a  a  a  a
     1  a  a  a  a  a
     2  a  a  a  a  a
     3  a  a  a  a  a
     4  a  a  a  a  a
    分析：N皇后问题就是指在一个N*N的棋盘上摆放N个皇后，要求皇后彼此之间不能相互攻击。当两个皇后在同行、同一列或同一斜线上时，我们称这两个皇后为相互攻击的。

    1、首先N个皇后放到N*N的棋盘上，那么至少先考虑不会发生行冲突的情况，那么N个皇后要均匀放到N行中，也就是说一行里面有且仅有一个皇后。那么在解决行冲突的情况下的全部放法有 n * n * n * ... * n == n ^ n 种放法
    2、所以接下来的思路就可以是一行一行的去放这个皇后，每一行的处理就是一次递归，而一行中这个皇后可能放的位置就是一次递归里面的for循环
    3、每当一行里面确定了一个皇后，那么就要把会与它冲突的列和斜线上的棋盘位置作为冲突位置，放后面行的皇后的时候不能再放这些位置，这样就保证了不会发生相互攻击。不考虑行冲突是因为一开始就解决了
    4、递归结束条件：当前递归深度N，找到了N个皇后的位置
    5、考虑剪枝：当前皇后的位置和之前已经摆放的皇后的位置有冲突，就剪枝，不再递归，返回
     */

    /**
     * <h3>方法一：dfs递归加回溯、剪枝</h3>
     * @param n 皇后个数，棋盘边长
     * @return 所有可能的皇后摆放方案
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        // 存储当前行的皇后位置
        char[] currentRowString = new char[n];
        Arrays.fill(currentRowString, '.');
        // 列冲突
        boolean[] columnConflict = new boolean[n];
        // 正斜线冲突，就是 / 这种
        boolean[] forwardSlashConflict = new boolean[2 * n - 1];
        // 反斜线冲突，就是 \ 这种
        boolean[] backwardSlashConflict = new boolean[2 * n - 1];
        // 函数处理
        dfs(0,
                result,
                new LinkedList<String>(),
                currentRowString,
                n,
                columnConflict,
                forwardSlashConflict,
                backwardSlashConflict);
        return result;
    }

    /**
     * 递归实现，运用了dfs递归和回溯的思想，剪枝
     * @param currentRow 当前递归处理的行号，从0开始
     * @param result 存储结果，所有可能的皇后摆放方案
     * @param solution 存储当前摆放所有皇后的方案
     * @param currentRowString 存储当前行的皇后位置的字符串，初始都是"...."
     * @param n 皇后个数
     * @param columnConflict 列冲突，存放的是那些列是与已摆放的皇后是冲突的
     * @param forwardSlashConflict 正斜线冲突 /，存放的是那些正斜线 / 是与已摆放的皇后是冲突的
     * @param backwardSlashConflict 反斜线冲突 \，存放的是那些反斜线 \ 是与已摆放的皇后是冲突的
     */
    private void dfs(int currentRow,
                     List<List<String>> result,
                     LinkedList<String> solution,
                     char[] currentRowString,
                     int n,
                     boolean[] columnConflict,
                     boolean[] forwardSlashConflict,
                     boolean[] backwardSlashConflict) {
        // 递归结束条件：当前递归深度N+1，已经处理了前面n行，找到了N个皇后的位置，添加当前方案
        if (currentRow == n){
            result.add(new ArrayList<>(solution));
            return;
        }
        // 尝试当前行的所有可能，当前递归层就是对应处理的就是多少行
        for (int j = 0; j < n; j++){
            // 如果当前位置和之前摆放的皇后有冲突，就剪枝，不再递归，for循环遍历下一个
            if (columnConflict[j]
                    || forwardSlashConflict[currentRow + j]
                    || backwardSlashConflict[j - currentRow + n - 1]) continue;
            // 不冲突，摆放皇后
            currentRowString[j] = 'Q';
            // 摆放皇后后，当前行已经确定，添加到solution中
            solution.push(new String(currentRowString));
            // 标记当前位置对应的列为冲突
            columnConflict[j] = true;
            // 标记当前位置对应的正斜线 / 为冲突
            forwardSlashConflict[currentRow + j] = true;
            // 标记当前位置对应的反斜线 \ 为冲突
            backwardSlashConflict[j - currentRow + n - 1] = true;
            // 处理下一行之前要把存储行的摆放的字符串还原
            currentRowString[j] = '.';
            // 递归处理下一行
            dfs(currentRow + 1,
                    result,
                    solution,
                    currentRowString,
                    n,
                    columnConflict,
                    forwardSlashConflict,
                    backwardSlashConflict);
            // 回溯
            solution.pop();
            columnConflict[j] = false;
            forwardSlashConflict[currentRow + j] = false;
            backwardSlashConflict[j - currentRow + n - 1] = false;
        }
    }
}
